package com.linzm.leetcode.primary.exercises1_20230114;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @Author zimingl
 * @Date 2023/1/15 17:13
 * @Description: 交替位二进制数
 * 输入：n = 5
 * 输出：true
 * 解释：5 的二进制表示是：101
 *
 * 做法：栈（连续）
 */
public class Demo21_693 {
    public static void main(String[] args) {
        Demo21_693 demo21_693 = new Demo21_693();
        int n = 5;
        boolean hasAlternatingBits = demo21_693.hasAlternatingBits2(n);
        System.out.println(hasAlternatingBits);
    }

    private boolean hasAlternatingBits(int n) {
        // 1-1 10-2 1010-10
        String s = Integer.toBinaryString(n);
        if (s.length() == 1) {
            return true;
        }
        Deque<Character> stack = new LinkedList<>();
        stack.push(s.charAt(0));
        for (int i = 1; i < s.length(); i++) {
            if (stack.peek() == s.charAt(i)) {
                return false;
            }
            stack.push(s.charAt(i));
        }
        return true;
    }

    public boolean hasAlternatingBits2(int n) {
        int prev = 2;
        while (n != 0) {
            int cur = n % 2;
            if (cur == prev) {
                return false;
            }
            prev = cur;
            n /= 2;
        }
        return true;
    }
}
